package com.kobeliu.entity;

/**
 * 剑指 10_1  快乐 从每天的简单题开始
 *
 * 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
 *
 * F(0) = 0,   F(1) = 1
 * F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
 *
 * 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
 *
 * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
 *
 * 示例 1：
 *
 * 输入：n = 2
 * 输出：1
 *
 * 示例 2：
 *
 * 输入：n = 5
 * 输出：5
 */

public class Demo_42_sword_10_1 {

    public static void main(String[] args) {

        System.out.println(fib(48));
    }

    public static int fib(int n) {
        if(n<2) return n;
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;

        int num = 2;
        while(num<=n){
            dp[num] = (dp[num-1]+dp[num-2]) %  1000000007;
            num++;
        }

        return dp[n];

    }
}
